//输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
//
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
//
//
//
// 示例 1：
//
//
//输入：n = 12
//输出：5
//
//
// 示例 2：
//
//
//输入：n = 13
//输出：6
//
//
//
// 限制：
//
//
// 1 <= n < 2^31
//
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/
// Related Topics 递归 数学 动态规划 👍 340 👎 0


package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

//Java：1～n 整数中 1 出现的次数
public class OneNzhengShuZhong1chuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new OneNzhengShuZhong1chuXianDeCiShuLcof().new Solution();
        // TO TEST
        // 这里有没有重复计算的可能
//        System.out.println(solution.countDigitOne(Integer.MAX_VALUE));
//        System.out.println(solution.singleDigitOne(Integer.MAX_VALUE));
        System.out.println(solution.countDigitOne(1014));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 每一个数字都存一下，大数据量肯定会爆
        public int countDigitOne(int n) {
            int digit = 1, res = 0;
            int high = n / 10, cur = n % 10, low = 0;
            while (high != 0 || cur != 0) {
                if (cur == 0) {
                    res += high * digit;
                } else if (cur == 1) {
                    res += high * digit + low + 1;
                } else {
                    res += (high + 1) * digit;
                }
                low += cur * digit;
                cur = high % 10;
                high = high / 10;
                digit = digit * 10;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
